package map;

public class MyHashMap {
    //使用Node表示哈希表中的链表节点

    static class Node{
        public int key;

        public int value;

        public Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    //一般数组的初始长度设置为素数，这样哈希冲突就会比较少
    private Node[] table = new Node[1001];

    private int size;

    //设置哈希函数，把key转为数组下标
    private int hashCode(int key){
        return key % table.length;
    }

    //哈希表的核心操作：
    //插入/修改键值对
    public void put(int key,int value){
        //1,根据key,来计算出下标的位置
        int index = hashCode(key);
        //2,遍历链表，看一下key是否在链表中已经存在了
        //如果存在，就修改对应的value
        Node head = table[index];
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.key == key){
                cur.value = value;
                return;
            }
        }
        //3,如果不存在，就直接插入，按照头插的方式
        Node newNode = new Node(key,value);
        newNode.next = head;
        table[index] = newNode;

        //4,插入完成后，size就要加1
        size++;
        if((double)size/table.length > 0.75){
            resize();
        }
    }

    //扩容操作
    public void resize(){
        Node []newTable = new Node[table.length * 2];
        //搬运，把原来table中所有的链表都搬运过来
        for(int i = 0;i < table.length;i++){
            for(Node cur = table[i];cur != null;cur = cur.next){
                //根据原有节点，创建新节点，插入到数组中去
                Node newNode = new Node(cur.key,cur.value);
                int newIndex = cur.key % newTable.length;
                //把新结点头插到新的链表中去
                newNode.next = newTable[newIndex];
                newTable[newIndex] = newNode;
            }
        }
        //用新的数组替换旧的
        table = newTable;
    }

    //根据键获取值
    public Integer get(int key){
        //1，根据key值，计算出下标
        int index = hashCode(key);
        //2,在对应的链表上找到该key的value值
        for(Node cur = table[index];cur != null;cur = cur.next){
            if(cur.key == key){
                return cur.value;
            }
        }
        //通过上述循环，如果没有找到，就返回null.
        return null;
    }

    //删除键值对
    public void remove(int key){
        //1,根据key找到下标
        int index = hashCode(key);
        //2,针对链表删除key的节点
        //a)先考虑链表为空的情况
        if(table[index] == null){
            //链表为空，就直接返回，不需要删除
            return;
        }
        //b)再考虑是否是头节点的情况
        if(table[index].key == key){
            table[index] = table[index].next;
            size--;
            return;
        }

        //c)一般情况下，我们遍历链表的时候把该节点的前一个节点也记录一下
        Node prev = table[index];
        Node cur = table[index].next;
        while(cur != null){
            if(cur.key == key){
                //触发删除操作
                prev.next = cur.next;
                size--;
                //由于hash表中的key是唯一的,在插入操作中也判断过了，因此只需删除一次即可
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}
